Deep neural networks are notorious for being sensitive to small well-chosen perturbations, and estimating the regularity of such architectures is of utmost importance for safe and robust practical applications. In this paper, we investigate one of the key characteristics to assess the regularity of such methods: the Lipschitz constant of deep learning architectures. First, we show that, even for two layer neural networks, the exact computation of this quantity is NP-hard and state-of-art methods may significantly overestimate it. Then, we both extend and improve previous estimation methods by providing AutoLip, the first generic algorithm for upper bounding the Lipschitz constant of any automatically differentiable function. We provide a power method algorithm working with automatic differentiation, allowing efficient computations even on large convolutions.

The paper studies the problem of estimating the Lipschitz constant of a mapping realized by a trained neural network. Several distinct contributions are made: (i) It is shown that exactly computing the Lipschitz constant of a two layer MLP (Multi Layer Preceptron) with ReLU activation is NP-hard (worst-case result). The algorithm, named AutoLip, is a generalization of multiplying spectral norms of Jacobians for a sequence of mappings, and hence usually provides pessimistic bounds. This technique assumes efficient implementation of the mapping in an auto-differentiable graph. It allows estimating the leading singular value of the transformation, which is equal to the Lipschitz constant.

Deep neural networks are notorious for being sensitive to small well-chosen perturbations, and estimating the regularity of such architectures is of utmost importance for safe and robust practical applications. In this paper, we investigate one of the key characteristics to assess the regularity of such methods: the Lipschitz constant of deep learning architectures. First, we show that, even for two layer neural networks, the exact computation of this quantity is NP-hard and state-of-art methods may significantly overestimate it. Then, we both extend and improve previous estimation methods by providing AutoLip, the first generic algorithm for upper bounding the Lipschitz constant of any automatically differentiable function. We provide a power method algorithm working with automatic differentiation, allowing efficient computations even on large convolutions.